I. Field of the Invention
The present invention relates to communications systems. More specifically, the present invention relates to systems for encoding and decoding data in digital communication systems.
II. Description of the Related Art
Communication systems facilitate transmission and reception of information from a source to a physically separate receiver. Mobile communications systems are typified by the movement of a receiver relative to a transmitter or vice versa. The communications link between transmitters and receivers in a mobile communications systems is characterized as a fading channel. Mobile satellite communications systems, having a transmitter on a spacecraft and a receiver on a ground based vehicle, cellular telephone systems and terrestrial microwave systems are examples of fading communications systems. A fading channel is a channel which is severely degraded. The degradation is due to numerous effects including multipath fading, severe attenuation due to the receipt via multiple paths of reflections of the transmitted signal off objects and structures in the atmosphere and on the surface. Other effects contributing to the impairment of the faded channel include Doppler shift due to the movement of the receiver relative to the transmitter and additive noise.
While both analog and digital communication methods have been used, digital methods afford several advantages including: improved immunity to channel noise and interference, increased capacity, and improved security of communication through the use of encryption.
Typically, an information signal is first converted into a form suitable for efficient transmission over the channel. Conversion or modulation of the information signal involves varying a parameter of a carrier wave on the basis of the information signal in such a way that the spectrum of the resulting modulated carrier is confined within the channel bandwidth. At a user location, the original message signal is replicated from a version of the modulated carrier received subsequent to propagation over the channel. Such replication is generally achieved by using an inverse of the modulation process employed by the source transmitter.
The field of data communications is particularly concerned with optimizing data throughput of a transmission system with a limited signal to noise ratio (SNR). The use of error correcting circuitry, such as encoders and decoders, allows system tradeoffs to be made with smaller SNRs or higher data rates to be used with the same bit error rate (BER).
One class of encoders is known as a convolutional encoder. As is well known in the art, a convolutional encoder converts a sequence of input data bits to a codeword based on a convolution of the input sequence with itself or with another signal. Coding rate and generating polynomials are used to define a convolutional code. Convolutional encoding of data combined with a Viterbi decoder is a well known technique for providing error correction coding and decoding of data.
Coding rate and constraint length are used to define a Viterbi decoder. A coding rate (k/n) corresponds to the number of coding symbols produced (n) for a given number of input bits (k). The coding rate of 1/2 has become one of the most popular rates, although other code rates are also generally used. A constraint length (K) is defined as the length of a shift register used in a convolutional encoding of data. A constraint length of seven (K=7) is typical in convolutional coding schemes. The convolutional encoder can be thought of as a Finite Impulse Response filter with binary coefficients and length K-1. This filter produces a symbol stream with 2.sup.-1 possible states.
The basic principle of the Viterbi algorithm is to take a convolutionally encoded data stream that has been transmitted over a noisy channel and use a finite state machine to efficiently determine the most likely sequence that was transmitted. The fundamental concept of a K=7 Viterbi decoder is that it is a machine that hypothesizes each of the possible 64 states that the encoder could have been in and determines the probability that the encoder transitioned from each of those states to the next set of 64 possible encoder states, given what was received. The probabilities are represented by quantities called metrics, which are proportional to the negative of the logarithm of the probability. Adding of the metrics is therefore the equivalent to the reciprocal of the product of the probabilities. Thus, smaller metrics correspond to higher probability events.
There are two types of metrics: state metrics, sometimes called path metrics; and branch metrics. The state metric represents the probability that the received set of symbols leads to the state with which it is associated. The branch metric represents the conditional probability that the transition from one state to another occurred assuming that the starting state was actually the correct state and given the symbol that was actually received.
There are two possible states leading to any other state, each corresponding to the occurrence of a zero or a one in the right-most bit of the convolutional encoder shift register. The decoder decides which is the more likely state by an add-compare-select (ACS) operation. Add refers to adding each state metric at the preceding level to the two branch metrics of the branches for the allowable transitions. Compare refers to comparing the pair of such metric sums for paths entering a state (node) at the given level. Select refers to selecting the greater of the two and discarding the other. Thus, only the winning branch is preserved at each node, along with the node state metric. If the two quantities being compared are equal, either branch may be selected, for the probability of erroneous selection will be the same in either case.
The Viterbi algorithm is a computationally efficient method of updating the conditional probabilities of the best state and the most probable bit sequence transmitted from the possible 2.sup.K-1 states. In order to compute this probability, all
2.sup.K-1 states for each bit must be computed. The resulting decision from each of these computations is stored as a single bit in a path memory.
A chain-back operation, an inverse of the encoding operation, is performed in which the C decision bits are used to select an output bit, where C is the chainback distance. After many branches the most probable path will be selected with a high degree of certainty. The path memory depth must be sufficiently long to be governed by the signal-to-noise ratio and not the length of the chain-back memory.
Though it is not necessary for analyzing either the code characteristics or the performance of the optimal decoder, it is useful in understanding both to exhibit the code on a trellis diagram. The term "trellis" is a term which describes a tree in which a branch not only bifurcates into two or more branches but also in which two or more branches can merge into one. A trellis diagram is an infinite replication of the state diagram for an encoder. The nodes (states) at one level in the trellis are reached from the node states of the previous level by the transition through one branch, corresponding to one input bit, as determined by the state diagram. Any codeword of a convolutional code corresponds to the symbols along a path (consisting of successive branches) in the trellis diagram.
Convolutional codes with Viterbi decoders have been used extensively to achieve reliable communication over power limited channels such as satellite communication systems and interference limited channels such as CDMA wireless communication systems. In a paper by G. Ungerboeck entitled "Channel Coding with Multilevel/Phase Signals", IEEE Transactions of Information Theory, Vol. IT-28, No. 1, January 1982, pp. 55-67, Ungerboeck used convolutional codes matched to two-dimensional signal constellations, to achieve coding gains of up to 6 dB (with respect to uncoded systems) over band limited channels. This technique is known as trellis coded modulation, and is widely used in data communication over voice-band telephone modems, digital transmission over coaxial cables, etc. G. D. Forney, Jr., in his treatise Concatenated Codes, Massachusetts Institute of Technology, 1966, developed a multilevel coding structure (consisting of a convolutional code and a block code) known as a concatenated code, which has been employed in deep space, resulting in very high coding gains.
The achievements mentioned above represent significant milestones in the continuing effort at reducing the gap between the performance of practical communication systems and the fundamental limits imposed by the Shannon Theorem. The Shannon limit refers to the minimum signal-to-noise ratio needed to communicate reliably over a given communication medium at a given spectral (bandwidth) efficiency. Recently, researchers have developed new classes of error correcting codes such as Turbo Codes and Serial Concatenated Interleaved Codes (SCIC), which provide further increases in performance over classical concatenated codes. These codes have been shown to achieve reliable communication at less than 1 dB above the Shannon limit. The use of Turbo Codes is described in a paper by C. Berrou entitled "Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes," Proceedings of ICC'93, Geneva, Switzerland, pp. 1064-1070, May 1993. Serial Concatenated Codes are described in S. Benedetto's paper "Serial Concatenation of Interleaved Codes: Performance Analysis, Design, and Iterative Decoding," TDA Progress Report 42-126.
The Turbo Codes as well as Serial Concatenated Codes employ iterative decoding schemes, in which each iteration uses one or more soft-decision output trellis decoders. The overwhelming success of these codes has refocused attention on soft decision trellis decoders. J. Hagenauer describes a soft output Viterbi algorithm (SOVA) using soft output metric decoders in his paper "Iterative (Turbo) Decoding of Systematic Concatenated Codes with MAP and SOVA Algorithms," Proceedings of the ITG Conference on Source and Channel Coding, Frankfurt Germany, pp. 1-9, October 1994. In addition, J Hagenauer describes a soft output Viterbi algorithm in his paper "Concatenated Viterbi Decoding", Proceedings of the Fourth Joint Swedish-Soviet Int. Workshop on Information Theory, Gotland Sweden, pp. 29-33, August 1989.
While MAP decoders offer significant performance gains over SOVA decoders, it is generally felt that SOVA decoders are simpler and faster. A particular limitation of the MAP approach is that it tends to be memory intensive. Hence, a need remains in the art for a soft output decision decoder which provides the superior performance of the MAP decoder while addressing the shortcomings and limitations of same.